Алгоритмічні основи криптології Лагун Андрій Едуардович 17/9/09 14:23 Лекція №1 Основні поняття і теореми
Відображення Задано дві множини X та Y. Нехай кожному ел-ту мн-ни X поставлено деякий елемент y=f(x) множини Y. В такому випадку задано відображення або ф-я f:X->Y із множини X у множину Y. Відобаження f:X->Y називається ін'єктивним, якщо воно різним аргументам співставляє різні значення:
,
Відображення з X в Y — сур'єктивне, якщо кожен елемент множини Y має праображ — такий ел-т x, що f(y)=x. Бієктивним є відображення,яке ін'єктивне і сур'єктивне одночасно. Тотожне відображення позначається
залишає елементи x на своїх місцях
. Відображення
назив. відображенням лівим оберненим до f:X->Y, за умови, що композиція
є тотожним відображенням, і правим оберненим
. Відображення g називається оберненим до f, якщо воно є одночасно і лівим і правим оберненим до f.
Властивості оберненого відображення 1. Відображення f:X->Y ін'єктивне тоді і тільки тоді, коли до нього існує ліве обернене. 2. Від. f:X->Y сур'єктивне тоді і тільки тоді, коли до нього існує праве обернене. 3. Якщо відображення f:X->Y бієктивне, то його ліве обернене збігається з правим оберненим. 4. У випадку, якщо множини X та Y — скінчені, і містять однакову к-ть елементів, то відображення f:X->Y має ліве обернене тоді і тільки тоді, коли воно має праве обернене.
Групи Групою називається множина G, наділена бінарною операцією * з такими властивостями: 1.
— асоціативність 2. В G існує нейтральний елемент e такий, що
3. Для кожного елемента x групи G іс Якщо підмножина H мн-и G утворює групу, відносно тієї ж операції *, то вона називається підгрупою групи G. Напр., множина раціональних чисел Q утворює групу за додаваням, якій нейтральний елемент 0, а обернений — протилежний, а множина цілих чисел Z є її підгрупою. Множина ++их раціональних чисел
утворює групу за множенням: e=1,
Якщо групова операція — множення, то група називається мультиплікативною, її нейтральний елемент є 1-ця, якщо операція ++я, група називається адетивною, нейтральний елемент, а обернений — протилежний елемент. Для ел-та x групи G
=x*x*x, де операція * виконана x-1 раз. В адетивній формі
. Для кожного ел-та x скінченої групи для деякого показника m виконується рівність
. Найменше з таких m називається порядком ел-та x в групі G. Порядком скінченої групи називається к-ть її елементів. Всі степені ел-та групи утворюють в ній підгрупу, порядок якої = порядку елемента. Нехай маємо 2 групи G і G' з операціями * і
відповідно. Відображення f:G->G' зберігає операцію, якщо
. Таке відображення називається гомоморфізмом з групи G в групу G'. Ядром гомоморфізму f:G->G' є мн-а всіх ел-ів G в які f відображає нейтральний ел-т групи G'. Наприклад, відображення, яке кожному цілому числу ставить у відповідність його остачу від ділення наснатуральне n є гомоморфізмом з адетивної групи
в адетивну групу
, ядро якого утворює цілі числа кратні n. Ядро гомоморфізму f:G->G' утворює в G підгрупу. Гоморфізм f:G->G' є ін'єктивним <=>, коли його ядро складається з нейтрального елемента групи G. Таке ядро називається тривіальним. Гомоморфізм, який є бієктивним відображенням називається ізоморфізмом. Напр., двійковий логарифм
задає ізоморфізм з мультиплікативної групи невід'ємних дійсних чисел
в адетивну групу всіх дійсних чисел
. Для груп G1 і G2 з операція * і
відповідно,
позначається їх прямий добуток. Множина пар (x1, x2), де
із покомпонентним. Результатом виконання операцій з компонентами x та y множин G вважається ел-т:
. Група називається комутативною або абелевою, якщо групова операція має властивість комутативності: Якщо кожен ел-т групи G є степенем її ел-та g, то цей ел-т називається твірним. Якщо група G має порядок n, то g є її твірним ел-том тоді і тільки тоді, коли його порядок також = n. Група, яка має твірний елемент називається циклічною. АЛГОРИТМИ ВИКОНАННЯ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
Розміщення в пам'яті комп'ютера довгих чисел та аналіз типів даних для виконання ар...